package algorithm.dynamic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 120. Triangle
 * leetcode: https://leetcode.com/problems/triangle/
 * Difficulty: Medium
 *
 * 给一个三角形的二维数组，找到从顶点到底部的最短路径，返回这个路径的长度。
 *
 * 举个栗子：
 * Input：
 * [
 *      [2],
 *     [3,4],
 *    [6,5,7],
 *   [4,1,8,3]
 * ]
 *
 * OutPut：11 （2+3+5+1 = 11）
 *
 * Created by yzy on 2019-03-30 17:50
 */
public class Triangle {

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(new Integer[]{2}));
        triangle.add(Arrays.asList(new Integer[]{3,4}));
        triangle.add(Arrays.asList(new Integer[]{6,5,7}));
        triangle.add(Arrays.asList(new Integer[]{4,1,8,3}));


        int min = minimumTotal(triangle);
        System.out.println(min);
    }


    /**
     * time   5ms beats 43.55%
     * memory     beats 82.52%
     * @param triangle
     * @return
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        int min =0;
        for(int level=0; level<triangle.size(); level++){
            List<Integer> rows = triangle.get(level);
            int levelMin = rows.get(0) + (level>0 ? triangle.get(level-1).get(0) : 0);
            for(int i=0; i<rows.size(); i++){
                int leftUpVal = i-1<0 ? Integer.MAX_VALUE : triangle.get(level-1).get(i-1);
                int rightUpVal = i>=level ? Integer.MAX_VALUE : triangle.get(level-1).get(i);
                int minVal = Math.min(leftUpVal, rightUpVal);
                minVal = minVal==Integer.MAX_VALUE ? 0 : minVal;
                int curr = rows.get(i) + minVal;
                rows.set(i,curr);
                levelMin = Math.min(curr, levelMin);
            }
            min = levelMin;
        }

        return min;
    }
}
